Пар производа у ранцу
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,25 s | 64 Mb | стандардни излаз | стандардни улаз |
Ненад је отпутовао у Париз и жели да купи поклоне својим родитељима. Пошто путује нискотарифном авио-компанијом, ограничена је маса коју може да понесе у свом ранцу. Оцу ће купити поклон у једној, а мајци у другој продавници. Напиши програм који на основу познатих маса и цена поклона у обе продавнице помаже Ненаду да родитељима купи што вредније поклоне (гледајући њихову укупну цену).
Улаз
Са стандардног улаза се уносе подаци у производима у две продавнице. За сваку продавницу се уноси број производа n (1≤n≤105), и затим у наредних n линија по два цела броја, сваки између 1 и 109, који представљају масу и затим цену производа. Након тога се уноси и укупна маса поклона коју је могуће понети у ранцу (цео број између 1 и 2⋅109).
Излаз
На стандардни излаз исписати највећи могући збир цена првог и другог поклона које је могуће понети у ранцу.
Пример
Улаз
3 2 4 3 6 4 5 3 2 3 3 2 4 5 6
Излаз
9
Овај задатак има и другачија решења у делу збирке који следи.
Морате бити улоговани како бисте послали задатак на евалуацију.